1. Field of the Invention
The present invention relates to a data packet transmission system wherein the data packets are transmitted from an input device to an output device through a switch engine. In particular, the present invention relates to a queue scheduling mechanism in such a data packet transmission system.
2. Background of the Invention
In today's world of telecommunications, characterized by an insatiable demand for bandwidth, there are two very fast growing technology sectors. These two technology sectors are the Internet and wireless communications. The Internet is primarily concerned with moving data while wireless communications is still mainly dealing with voice transmission. However, all of this is changing very rapidly. Service providers of all types tend to offer more services in an attempt to become, or to remain, profitable. Service offerings range from long distance transport of voice and data over high-speed data backbone to the Internet and data services being offered on wireless pieces of equipment especially wireless phones of second and third generations.
Voice has long been transported in the form of data on circuit-switched Time Division Multiplexed (TDM) networks which are very different from the Internet packet networks obeying the Internet Protocol (IP). TDM is a connection oriented network while IP is connectionless. Hence, TDM can offer the carrier-grade type of service required by delay-sensitive applications, such as voice, while IP is well adapted to the transport of data.
All specialized transport network operators want to converge to a similar “one-fits-all” type of network, i.e. a packet network able to process different flows of data depending on Quality of Service (QoS) schemes so that flows are indeed processed according to some specific requirements such as delay, jitter, bandwidth, and packet loss.
Switching and routing have been opposed due to the manner in which data packets flow through the nodes of the network. Switching is tightly associated to connection oriented protocols like ATM and requires that a path be established prior to any data movement while routing is essentially the mode of operation of IP, and its hop-by-hop moving of data packets, with a decision to be made at each node. However, the end result is that whichever access protocol is in use, the networks are in actuality becoming switched-packet networks.
When packets arrive in a node, the layer 2 forwarding component of the switching node searches a forwarding table to make a routing decision for each packet. Specifically, the forwarding component examines information contained in the packet's header, searches the forwarding table for a match, and directs the packet from the input interface to the output interface across the switch engine.
Generally, a switching node includes a plurality of output queues corresponding respectively to the plurality of output adapters and a shared memory for temporarily storing the incoming packets to be switched. The switch architecture is known to potentially provide the best possible performance allowing a full outgoing throughput utilization with no internal blocking and minimum delay.
Every queue is also organized by priority. That is, incoming packet headers, which carry a priority tag, are inspected not only to temporarily store packets in different queues, according to the output ports they are due to leave the switch engine but also are sorted by priority within each queue so that higher priority packets are guaranteed to be admitted first in the shared memory, getting precedence over lower priority traffic. In turn, the switch engine applies the same rule to the admitted packets, always privileging higher priorities. This is achieved by organizing the output queues by priority too. Hence, packet pointers, in each output queues are sorted so that admitted packets of higher priorities exit the switch engine first even though older packets, yet of a lower priority, are still waiting.
The priorities associated with the data packets are fully pre-emptive. Thus, if there are four priorities from P0 to P3, priority P0 is going to take immediate precedence over any other traffic at priorities P1-P3 and so on. This is definitely a feature necessary to be able to handle a mix of voice and real-time traffic along with “pure” data traffic over a single network. This guarantees that data for the voice and real-time type of applications are handled with no delay so that there is no latency other than the necessary minimum time to traverse the switch engine and, even more importantly, in order that no significant jitter be added to any flow of real-time packets. However, this is necessarily done at the expense of lower priority traffic which has, in case of congestion, to wait. Even if this is not a problem since the transfer of data files is normally insensitive to delay and jitter, a lower priority (e.g. P3) may be completely starved by higher priorities (e.g. P0-P2).